import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-24
 * Time: 20:35
 */
public class TestDemo {

    /**
     * 给定一个有序整型数组, 实现二分查找
     * @param args
     */
    public static int binarySearch(int[] array,int key) {
        int left =0;
        int right =array.length-1;
        while(left<=right) {
            int mid = (left+right)>>>1;
            if(array[mid]>key) {
                right=mid-1;
            }else if (array[mid]<key) {
                left=mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    public static void main1(String[] args) {
        int[] array = {1,2,3,4,5,6,7,8,9,0};
        int key = 7;
        int ret = binarySearch(array, key);
        if(ret==-1) {
            System.out.println("没找到");
        }else {
            System.out.print("找到了，下标为："+ret);
        }
    }

    /**
     * 给定一个整型数组, 判定数组是否有序（递增）
     * @param args
     */
    public static boolean isArraySort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if(array[i-1]>array[i]) {
                return false;
            }
        }
        return true;
    }
    public static void main2(String[] args) {
        int[] array ={1,2,3,3,5,5,6,7,8,9};
        if(isArraySort(array)) {
            System.out.print(Arrays.toString(array));
            System.out.println("该数组有序");
        }else {
            System.out.print(Arrays.toString(array));
            System.out.println("该数组无序");
        }
    }

    /**
     *给定一个整型数组, 实现冒泡排序(升序排序)
     * @param args
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]) {
                    int tmp =array[j];
                    array[j]=array[j+1];
                    array[j+1] =tmp;
                    flag=true;
                }
            }
            if(flag==false) {
                break;
            }
        }
    }
    public static void main3(String[] args) {
         int[] array = {78,1,2,38,58,66,5,20,18,96,30,5,3,9,7,4};
         bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     * 输入: [4,1,2,1,2]
     * 输出: 4
     * 输入: [2,2,1]
     * 输出: 1
     * @param args
     */
    public static int onlyOnceAppearElement(int[] array) {
        //遍历数组进行按位异或
        //按位异或相同的全部抵消最后只剩下单个的元素
        int ret  =0;
        for (int i = 0; i < array.length; i++) {
            ret^=array[i];
        }
        return ret;
    }
    public static void main(String[] args) {
          int[] array = {4,1,2,1,2,4,5};
        System.out.println(onlyOnceAppearElement(array));
    }

}
